An Alexander-Determinant-PolyTime Puzzle
July-26-09
2:15 AM
Why is the Alexander polynomial computable in polynomial time? There are determinant formulas for the Alexander polynomial, and hence it is computable in polynomial time using Gaussian elimination. Yet the intermediate steps seen along the way, while doing row/column reduction, have no knot theoretic interpretation that I know of. So to quickly compute the Alexander polynomial one has to exit knot theory. Since this contradicts my beliefs, it must be that the intermediate steps do have a knot theoretic interpretation that I simply don't understand yet. Time to find it!
Why should I care? Extensions to tangles have fundamental importance. They provide the "right" way to prove invariance under Reidemeister and other moves, and, I believe, they are necessary if there's any hope of categorification. Yet Jana's pA and every other such extension that I know of are exponential time. (Perhaps except for the Burau extension to braids, which ends in a determinant). This means that these extensions miss something fundamental about the Alexander polynomial, and it will be nice to "catch" that thing.
From [link]: